package com.HeapSort;

import java.util.Arrays;

public class HeapSort {
    public static void main(String[] args) {
//        int arr[] = {4,6,8,5,9};
//        heapSort(arr);
        int[] arr = new int[80000];
        for (int i = 0 ; i < arr.length;i++){
            //  random()参数[0,1)之间的数
            arr[i] = (int) (Math.random()*200000);
        }
        long strat = System.currentTimeMillis();
        //int[] temp = new int[arr.length];
        //887
        //quickSort(arr,0,arr.length-1);
        //1737
        heapSort(arr);
        long end = System.currentTimeMillis();

        System.out.println("耗时："+(end-strat));
    }
    /**
     * 堆排序
     * 时间复杂度 O(nlogn),8w数据测试：18ms
     */
    public static void heapSort(int[] arr){
        for(int i = arr.length/2-1;i>= 0 ;i--){
            adjustHeap(arr,i,arr.length);
//            System.out.println(Arrays.toString(arr));
        }

        for(int j = arr.length-1 ; j > 0 ; j--){
            //将最大的元素后末尾的元素交换
            swap(arr,0,j);
            //在交换之前，已经构建好了大顶堆，数组满足大顶堆的特性
            //交换以后，只变动了根结点，其他位置非叶子结点的子树仍是有序的，所以交换后只需要针对变动的根结点进行重新排序，所以i=0
            adjustHeap(arr,0,j);

        }


    }

    /**
     * 调整大顶堆
     * @param arr 待排序的数组
     * @param i 非叶子结点在数组中的索引
     * @param length 需要调整元素最后一个元素的下标
     *               第一次调整length = arr.length，最后将最大值交换到末尾
     *               第二次调整就不用管最后一个元素了，对length = arr.length -1
     */
    public static void adjustHeap(int[] arr,int i,int length){
        //保存索引的值用于交换
        int temp = arr[i];
        //从左子结点开始进行比较，交换后的结点可能仍然具有孩子结点，所以应该通过循环以该结点为根结点的子树上的所有结点
        for(int k = 2*i+1; k < length ; k = 2*k + 1){
            /*
            比较出该节点以及左右两个孩子结点中的最大值
            在一个非叶子结点中，一定先有左孩子结点，当不一定有右孩子结点，所以需要进行判断k+1是否超过需要调整的元素个数
            */
            if(k+1 < length && arr[k] < arr[k+1]){
                k++;
            }
            /*
            如果左右孩子结点的值比该结点的值大，就将该子节点的值赋给根节点（不是交换
            在整个循环比较的过程中,temp始终保持根节点值arr[i]
            i记录最后交换的位置
            如果没有发生交换，说明这个子数已经符合大顶堆了（后面的子树肯定也符合，则直接break退出
             */
            if(temp < arr[k]){
                arr[i] = arr[k];
                i = k;
            }else {
                break;
            }
        }
        //for循环结束后，已经调整好以该结点为根结点下子树的顺序，最后将temp放在最终位置
        arr[i] = temp;
    }

    public static void swap(int[] arr,int start,int end){
        int temp = arr[start];
        arr[start] = arr[end];
        arr[end] = temp;
    }
}
